package 系统复习.面试题.区间集合;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
 */
public class L253 {

    public int minMeetingRooms(int[][] intervals) {

        int[] ints = new int[1000000];
        for (int i = 0; i < intervals.length; i++) {
            for (int j = intervals[i][0]; j < intervals[i][1]; j++) {
                ints[j]++;
            }
        }
        int max = 0;
        for (int i = 0; i < ints.length; i++) {
            max = Math.max(max, ints[i]);
        }
        return max;

    }

    //  优先队列+排序
    // 如果队列里有比下一个会议开始时间早结束的之前的会议，则下一个会议直接使用之前的会议室。否则，加入新的的会议结束时间。
    public int minMeetingRooms1(int[][] intervals) {
        if(intervals == null || intervals.length == 0) {
            return 0;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        q.add(intervals[0][1]);
        for(int i = 1; i < intervals.length; i++){
            if(q.peek() <= intervals[i][0]){
                q.poll();
            }
            q.add(intervals[i][1]);
        }
        return q.size();
    }

    public static void main(String[] args) {
        L253 l253 = new L253();
        System.out.println(l253.minMeetingRooms(new int[][]{{0, 30}, {5, 10}, {15, 20}}));
    }
}
